//给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
//
//
//
// 示例 1：
//
//
//
//
//输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
//输出：6
//解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
//
//
// 示例 2：
//
//
//输入：height = [4,2,0,3,2,5]
//输出：9
//
//
//
//
// 提示：
//
//
// n == height.length
// 0 <= n <= 3 * 104
// 0 <= height[i] <= 105
//
// Related Topics 栈 数组 双指针 动态规划
// 👍 2410 👎 0

/**
 * @author DaHuangXiao
 */
package leetcode.editor.cn;

import java.util.LinkedList;

public class TrappingRainWater {
    public static void main(String[] args) {
        Solution solution = new TrappingRainWater().new Solution();
        System.out.println(solution.trap(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        //  单调栈，逐行计算
        //  举例 3，2，1，0，1，2，3
        //  3，2，1，0 入栈后，遇到 1，则意味着可以蓄水了，蓄水量为 wid * hei
        //  wid根据下标index可以计算出 4 - 2 + 1 = 3
        //  hei = 1-0
        //  十分巧妙的思路
        public int trap(int[] height) {
            LinkedList<Integer> stack = new LinkedList<>();
            int res = 0;

            for (int i = 0; i < height.length; i++) {
                while (!stack.isEmpty() && height[i] > height[stack.getLast()]) {
                    int top = stack.pollLast();
                    if (stack.isEmpty()) {
                        break;
                    }
                    int top2 = stack.getLast();
                    int curWid = i - top2 - 1;
                    int curHeight = Math.min(height[i], height[top2]);

                    res += curWid * (curHeight - height[top]);
                }
                stack.addLast(i);
            }
            return res;

        }
    }
//leetcode submit region end(Prohibit modification and deletion)
//
}